class Solution {
    public int maxProfit(int c, int[] prices) {
        int n = prices.length;
        int[] temp = new int[n+1];
        System.arraycopy(prices, 0, temp, 1, n);
        temp[0] = 0;
        prices = temp;
        int[][][] f = new int[2][2][c+1];
        Arrays.fill(f[0][0], -1000000);
        Arrays.fill(f[0][1], -1000000);
        Arrays.fill(f[1][0], -1000000);
        Arrays.fill(f[1][1], -1000000);
        f[0][0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= 1; j++) {
                for (int k = 0; k <= c; k++) {
                    if (j == 0) {
                        f[i&1][0][k] = Math.max(f[i&1][0][k], f[(i-1)&1][1][k] + prices[i]);
                    } else if (j == 1 && k >= 1) {
                        f[i&1][1][k] = Math.max(f[i&1][1][k], f[(i-1)&1][0][k-1] - prices[i]);
                    }
                    f[i&1][j][k] = Math.max(f[i&1][j][k], f[(i-1)&1][j][k]);
                }
            }
        }
        return Arrays.stream(f[n&1][0]).boxed().max(Comparator.comparingInt(i -> i)).orElse(0);
    }
}
